{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #分割回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCut"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code>，请将 <code>s</code> 分割成一些子串，使每个子串都是回文串。</p>\n",
    "\n",
    "<p>返回符合要求的 <strong>最少分割次数</strong> 。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;aab&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只需一次分割就可将&nbsp;s<em> </em>分割成 [&quot;aa&quot;,&quot;b&quot;] 这样两个回文子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;a&quot;\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;ab&quot;\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 132&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/palindrome-partitioning-ii/\">https://leetcode-cn.com/problems/palindrome-partitioning-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [omKAoA](https://leetcode.cn/problems/omKAoA/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [omKAoA](https://leetcode.cn/problems/omKAoA/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aab\"', '\"a\"', '\"ab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        t = '#' + '#'.join(s) + '#'\n",
    "        n = len(t)\n",
    "        c, sight = 0, 0\n",
    "        lens = [0] * n\n",
    "        dp = [0] + list(range(n-1))\n",
    "        for i in range(n):\n",
    "            arm = min(max(sight - i, 0), lens[2 * c - i]) \n",
    "            while i + arm < n and i - arm >= 0 and t[i + arm] == t[i - arm]:\n",
    "                dp[i + arm] = min(dp[i + arm], dp[i - arm] + 1)\n",
    "                arm += 1\n",
    "            lens[i] = arm - 1\n",
    "            if arm + i > sight:\n",
    "                c = i\n",
    "                sight = arm + i\n",
    "        return dp[-1] - 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if s == s[::-1]: return 0\n",
    "        res = float('inf')\n",
    "        for i in range(1, len(s) + 1):\n",
    "            if s[:i] == s[:i][::-1]:\n",
    "                res = min(self.minCut(s[i:]) + 1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        recur_lens = [[1] for _ in range(len(s))]\n",
    "        for i in range(1,len(s)):\n",
    "            cur_lens = [1]\n",
    "            if s[i] == s[i-1]:\n",
    "                cur_lens.append(2)\n",
    "            \n",
    "            if i >= 2:\n",
    "                for l in recur_lens[i-1]:\n",
    "                    j = i - l - 1\n",
    "                    if j >= 0:\n",
    "                        if s[i] == s[j]:\n",
    "                            cur_lens.append(l+2)\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            recur_lens[i] = cur_lens\n",
    "        \n",
    "        dp = [0] * len(s)\n",
    "        for i in range(1,len(s)):\n",
    "            mincut = None\n",
    "            for l in recur_lens[i]:\n",
    "                j = i-l\n",
    "                if j >= 0:\n",
    "                    cut = 1 + dp[j]\n",
    "                else:\n",
    "                    cut = 0\n",
    "                if mincut is None or cut < mincut:\n",
    "                    mincut = cut\n",
    "            dp[i] = mincut\n",
    "        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        lis=[]\n",
    "        self.makearr(s,lis)\n",
    "        dp0=[-1]*(len(s)+1)\n",
    "        dp0[0]=-1\n",
    "        dp0[1]=0\n",
    "        for i in range(1,len(s)):\n",
    "            min0=2001\n",
    "            for j in range(i,-1,-1):\n",
    "                if lis[i][j]:\n",
    "                    now=dp0[j]+1\n",
    "                    min0=min(min0,now)\n",
    "            dp0[i+1]=min0\n",
    "        return dp0[-1]\n",
    "\n",
    "    def makearr(self,s,lis):\n",
    "        for j in range(len(s)):\n",
    "            lis2=[]\n",
    "            for i in range(0,j+1):\n",
    "                if i==j:\n",
    "                    lis2.append(1)\n",
    "                elif s[i]==s[j]:\n",
    "                    if j==i+1:\n",
    "                        lis2.append(1)\n",
    "                    else:\n",
    "                        lis2.append(lis[j-1][i+1])\n",
    "                else:\n",
    "                    lis2.append(0)\n",
    "            lis.append(lis2[:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # f[n]: s[:n] 的最少分割次数\n",
    "        # g[n]: s[:n] 的最后一个回文字符串的可能起始位置\n",
    "        f = [0] * (len(s) + 1)\n",
    "        g = [[] for _ in range(len(s) + 1)]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            l = r = i            \n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                g[r + 1].append(l)\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            l, r = i, i + 1\n",
    "            while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "                g[r + 1].append(l)\n",
    "                l -= 1\n",
    "                r += 1\n",
    "\n",
    "        for n in range(1, len(s) + 1):\n",
    "            f[n] = f[n - 1] + 1\n",
    "            for l in g[n]:\n",
    "                if l == 0:\n",
    "                    f[n] = 0\n",
    "                else:\n",
    "                    f[n] = min(f[n], f[l] + 1)\n",
    "               \n",
    "        return f[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        d=collections.defaultdict(list)\n",
    "        for i in range(len(s)):\n",
    "            d[i].append(i)\n",
    "            for oddLen in range(1,min(i,len(s)-i-1)+1):\n",
    "                if s[i-oddLen]!=s[i+oddLen]:\n",
    "                    break\n",
    "                d[i-oddLen].append(i+oddLen)\n",
    "            for evenLen in range(min(i,len(s)-i-2)+1):\n",
    "                if s[i-evenLen]!=s[i+1+evenLen]:\n",
    "                    break\n",
    "                d[i-evenLen].append(i+1+evenLen)\n",
    "        que,visited=set(),set()\n",
    "        que.add(0)\n",
    "        res=0\n",
    "        while que:\n",
    "            tmp=set()\n",
    "            for q in que:\n",
    "                if q in visited:\n",
    "                    continue\n",
    "                if q==len(s):\n",
    "                    return res-1\n",
    "                visited.add(q)\n",
    "                for nxt in d[q]:\n",
    "                    tmp.add(nxt+1)\n",
    "            res+=1\n",
    "            que=tmp\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#分割回文串 II，最小分割次数，输入：s = \"aab\"输出：1；输入：s = \"ab\"输出：1\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        #dp预处理，每个子串是否为回文串\n",
    "        n=len(s)\n",
    "        dp=[[True]*n for i in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j]=(s[i]==s[j]) and dp[i+1][j-1]\n",
    "        ans=[float('inf')]*n #ans[i]表示s[0..i]的最少分割次数\n",
    "        for i in range(n):\n",
    "            if dp[0][i]:ans[i]=0#本身已经是一个回文串了\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if dp[j+1][i]:ans[i]=min(ans[i],ans[j]+1)\n",
    "        return ans[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        isPal = [[False for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n): isPal[i][i] = True\n",
    "        for j in range(n): # (i,j)\n",
    "            for i in range(j):\n",
    "                isPal[i][j] = (s[i] == s[j]) and (isPal[i+1][j-1] if j-i>1 else True)\n",
    "        dp = [sys.maxsize for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        for j in range(n):\n",
    "             for i in range(j+1):\n",
    "                if isPal[i][j]:\n",
    "                    dp[j] = min(dp[j], dp[i-1]+1 if i-1>=0 else 0)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]  # 代表s[i:j+1]是否为回文串\n",
    "        pandrome_dict = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "            pandrome_dict[i].append(i)\n",
    "            if i != n-1:\n",
    "                if s[i] == s[i+1]:\n",
    "                    dp[i][i+1] = 1\n",
    "                    pandrome_dict[i+1].append(i)\n",
    "                \n",
    "        for j in range(1, n):\n",
    "            for i in range(j-1):\n",
    "                if (dp[i+1][j-1] == 1) and (s[i] == s[j]):\n",
    "                    dp[i][j] = 1\n",
    "                    pandrome_dict[j].append(i)\n",
    "                    # print(pandrome_dict)\n",
    "        # print(pandrome_dict)\n",
    "        shortest_cut = [i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in pandrome_dict[i]:\n",
    "                if j == 0:\n",
    "                    shortest_cut[i] = 0\n",
    "                else:\n",
    "                    shortest_cut[i] = min(shortest_cut[i], shortest_cut[j-1]+1)\n",
    "        # print(shortest_cut)\n",
    "        return shortest_cut[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[True] * n for _ in range(n)]\n",
    "\n",
    "        # 第i行第j列记录s[i:j+1]子串是否为回文字符串\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]\n",
    "\n",
    "        # 建图\n",
    "        nexts = [[] for _ in range(n)]\n",
    "        for start in range(n):\n",
    "            for stop in range(start, n):\n",
    "                if g[start][stop]:\n",
    "                    nexts[start].append(stop)\n",
    "\n",
    "        def bfs():\n",
    "            queue = deque([0])\n",
    "            count = -1\n",
    "            visited = [False] * n\n",
    "            while queue:\n",
    "                count += 1\n",
    "                for _ in range(len(queue)):\n",
    "                    start = queue.popleft()\n",
    "                    for stop in nexts[start]:\n",
    "                        if not visited[stop]:\n",
    "                            if stop == n-1:\n",
    "                                return count\n",
    "                            visited[stop] = True\n",
    "                            queue.append(stop+1)\n",
    "        return bfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        mem_p = {}\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            mem_p[i] = set()\n",
    "            mem_p[i].add(i)\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                mem_p[i].add(i-1)\n",
    "        for lens in range(2, len(s)):\n",
    "            for i in range(len(s)-lens):\n",
    "                j = i+ lens\n",
    "                if s[i] == s[j]:\n",
    "                    if i+1 in mem_p[j-1]:\n",
    "                        mem_p[j].add(i)\n",
    "\n",
    "        count_dic = {-1:0}\n",
    "        for j in range(len(s)):\n",
    "            mini_val = len(s)\n",
    "            for i in mem_p[j]:\n",
    "                cur_val = count_dic[i-1]\n",
    "                if i != 0:\n",
    "                    cur_val += 1\n",
    "                mini_val = min(mini_val, cur_val)\n",
    "            count_dic[j] = mini_val\n",
    "        return count_dic[len(s)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        f=[[False]*(n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if j==i or (j+1==i and s[j]==s[i]):\n",
    "                    f[j][i]=True\n",
    "                elif s[j]==s[i] and f[j+1][i-1]:\n",
    "                    f[j][i]=True                     \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            ans=inf\n",
    "            for j in range(i,-1,-1):\n",
    "                if f[j][i]:\n",
    "                    ans=min(ans,dfs(j-1)+1)\n",
    "            return ans\n",
    "        return dfs(n-1)-1\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        f=[[False]*(n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if j==i or (j+1==i and s[j]==s[i]):\n",
    "                    f[j][i]=True\n",
    "                elif s[j]==s[i] and f[j+1][i-1]:\n",
    "                    f[j][i]=True                     \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            ans=inf\n",
    "            for j in range(i,-1,-1):\n",
    "                if f[j][i]:\n",
    "                    ans=min(ans,dfs(j-1)+1)\n",
    "            return ans\n",
    "        return dfs(n-1)-1\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        t = [[True]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                t[i][j] = s[i] == s[j] and t[i+1][j-1]\n",
    "        dp = [[2000]*(n+1) for _ in range(n+1)]\n",
    "        for row in dp:\n",
    "            row[0] = -1\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(1, j+1):\n",
    "                if t[i-1][j-1]:\n",
    "                    dp[1][j] = min(dp[1][i-1]+1, dp[1][j])\n",
    "        return dp[1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        \n",
    "        # 先获取数组中回文子串的情况\n",
    "        def max_huiwen_substring(string):\n",
    "            # 如果string[i]==string[j]，那么dp[i][j]=dp[i+1][j-1]\n",
    "            # 否则的话，dp[i][j]=False\n",
    "            dp=[[0 for _ in range(len(string))] for _ in range(len(string))]\n",
    "            max_len=0\n",
    "            #dp中左下角的值无意义，对角线置为1\n",
    "            for i in range(len(string)):\n",
    "                dp[i][i]=True\n",
    "                max_len=1\n",
    "\n",
    "            for i in range(len(string)-2,-1,-1):\n",
    "                for j in range(i+1,len(string)):\n",
    "                    if string[i]==string[j]:\n",
    "                        if i+1<=j-1:\n",
    "                            dp[i][j]=dp[i+1][j-1]\n",
    "                        else:\n",
    "                            dp[i][j]=True\n",
    "                    else:\n",
    "                        dp[i][j]=False\n",
    "                    if dp[i][j]:\n",
    "                        if j-i+1>max_len:\n",
    "                            max_len=j-i+1\n",
    "\n",
    "            return dp\n",
    "\n",
    "        def is_huiwen(dp,i,j):\n",
    "            return dp[i][j]\n",
    "\n",
    "        def get_minist_splits(string,end,dp,dp_2):   \n",
    "            if end==len(string)-1:   #当只有一个字符的时候，那么不需要进行分割，直接返回0\n",
    "                return 0\n",
    "            if dp[end][len(string)-1]:\n",
    "                return 0\n",
    "            if dp_2[end][len(string)-1]!=None:\n",
    "                return dp_2[end][len(string)-1]\n",
    "            res=float('inf')\n",
    "            for i in range(end,len(string)):\n",
    "                if dp[end][i]:  #如果end...i是回文，那么可以将end...i作为一个回文分支，剩下的i+1...len(string)-1递归进行\n",
    "                    res=min(res,1+get_minist_splits(string,i+1,dp,dp_2))\n",
    "            dp_2[end][len(string)-1]=res\n",
    "            return dp_2[end][len(string)-1]\n",
    "        string=s\n",
    "        dp=max_huiwen_substring(string)\n",
    "        if dp[0][len(string)-1]:\n",
    "            return 0\n",
    "        dp_2=[[None for _ in range(len(string))] for _ in range(len(string))]\n",
    "        res=get_minist_splits(string,0,dp,dp_2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        '''\n",
    "        n = len(s)\n",
    "        dp = [float('inf')] * n\n",
    "        dp[0] = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(i, -1, -1):\n",
    "                cur = s[j: i + 1]\n",
    "                if cur == cur[::-1]:\n",
    "                    if j == 0:\n",
    "                        dp[i] = 0\n",
    "\n",
    "                    dp[i] = min(dp[i], dp[j - 1] + 1)\n",
    "        \n",
    "        return dp[-1]\n",
    "        '''\n",
    "        n = len(s)\n",
    "        dp = [i for i in range(n)]\n",
    "\n",
    "        set_ = set()           # 是回文的 (left, right) pair\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            set_.add((i, i))\n",
    "            for j in range(i + 1, n):\n",
    "                if j - i == 1 and s[i] == s[j]:\n",
    "                    set_.add((i, j))\n",
    "                elif s[i] == s[j] and (i + 1, j - 1) in set_:\n",
    "                    set_.add((i, j))\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, -1, -1):\n",
    "                if (j, i) in set_:\n",
    "                    if j == 0:\n",
    "                        dp[i] = 0\n",
    "                    else:\n",
    "                        dp[i] = min(dp[i], dp[j - 1] + 1)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check_palindrome(s: str) -> bool:\n",
    "    return s == s[::-1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        palindrome_dict = dict()\n",
    "        n = s.__len__()\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i):\n",
    "                if check_palindrome(s[j:i]):\n",
    "                    palindrome_dict[(j, i)] = 1\n",
    "        dp = [sys.maxsize] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if (0, i + 1) in palindrome_dict:\n",
    "                dp[i] = 0\n",
    "                continue\n",
    "            for j in range(i):\n",
    "                if (j + 1, i + 1) in palindrome_dict:\n",
    "                    dp[i] = min(dp[i], dp[j] + 1)\n",
    "        return dp[-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        isPal = defaultdict(lambda:defaultdict(lambda:False))\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1):\n",
    "                ch1 = s[i]\n",
    "                ch2 = s[j]\n",
    "                if ch1 == ch2 and (i == j or i == j+1 or (isPal[j+1][i-1] is True)):\n",
    "                    isPal[j][i] = True\n",
    "        dp = []\n",
    "        for i in range(len(s)):\n",
    "            if isPal[0][i]:\n",
    "                dp.append(0)\n",
    "            else:\n",
    "                dp.append(i)\n",
    "                for j in range(1, i+1):\n",
    "                    if isPal[j][i]:\n",
    "                        dp[i] = min(dp[i], dp[j-1]+1)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        #先找出所有的回文串，以开始index，结尾index的方式存储，以结尾index排序\n",
    "        paralist = []\n",
    "        for i in range(len(s)):\n",
    "            j, k = i, i\n",
    "            paralist.append((j, k))\n",
    "            while j > 0 and k < len(s) - 1 and s[j - 1] == s[k + 1]:\n",
    "                j -= 1\n",
    "                k += 1\n",
    "                paralist.append((j, k))\n",
    "            j, k = i, i + 1\n",
    "            if k >= len(s) or s[j] != s[k]:\n",
    "                continue\n",
    "            else:\n",
    "                paralist.append((j, k))\n",
    "            while j > 0 and k < len(s) - 1 and s[j - 1] == s[k + 1]:\n",
    "                j -= 1\n",
    "                k += 1\n",
    "                paralist.append((j, k))\n",
    "\n",
    "        paralist = sorted(paralist, key = lambda x:x[1])\n",
    "\n",
    "        dp = [len(s)] * (len(s) + 1)\n",
    "        dp[0] = 0\n",
    "        p = 0\n",
    "        for i in range(len(s)):\n",
    "            while( p < len(paralist) and paralist[p][1] == i):\n",
    "                dp[i + 1] = min(dp[i + 1], dp[paralist[p][0]] + 1)\n",
    "                p += 1\n",
    "            \n",
    "        return dp[-1] - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        m = len(s)\n",
    "\n",
    "        # 判断回文，存储到hashmap\n",
    "        seen = set()\n",
    "        for i in range(m):\n",
    "            left = i\n",
    "            right = i\n",
    "            while left >= 0 and right < m:\n",
    "                if s[left] != s[right]:\n",
    "                    break\n",
    "                seen.add((left, right))\n",
    "                left -= 1\n",
    "                right += 1\n",
    "        for i in range(m):\n",
    "            left = i\n",
    "            right = i + 1\n",
    "            while left >= 0 and right < m:\n",
    "                if s[left] != s[right]:\n",
    "                    break\n",
    "                seen.add((left, right))\n",
    "                left -= 1\n",
    "                right += 1\n",
    "\n",
    "        # 动规判断回文子串；状态转移方程为dp[i] = min(dp[i], dp[j] + 1) for j in range(i + 1) if s[j: i + 1] if in seen\n",
    "        dp = [i - 1 for i in range(m + 1)]  # dp[0] = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1):\n",
    "                if (j, i) in seen:\n",
    "                    dp[i + 1] = min(dp[i + 1], dp[j] + 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        hashtale = {}\n",
    "        for j in range(2*len(s)-1):\n",
    "            l, r = j//2, j//2 + j%2\n",
    "            while l>=0 and r <len(s) and s[l] == s[r]:\n",
    "                hashtale[(l,r)] = 1\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        dp = {}\n",
    "        for i in range(len(s)):\n",
    "            if hashtale.get((0,i)):\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                dp[i] = 10000\n",
    "                for j in range(1, i+1):\n",
    "                    if hashtale.get((j,i)):\n",
    "                        dp[i] = min(dp[i], dp[j-1]+1)\n",
    "        return dp[len(s)-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        t = [[True]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                t[i][j] = s[i] == s[j] and t[i+1][j-1]\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for row in dp:\n",
    "            row[0] = -1\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(1, j+1):\n",
    "                if t[i-1][j-1]:\n",
    "                    dp[1][j] = min(dp[1][i-1]+1, dp[1][j])\n",
    "                else:\n",
    "                    dp[i][j] = j-i\n",
    "                    dp[1][j] = min(dp[1][i-1]+dp[i][j]+1, dp[1][j])\n",
    "        return dp[1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            return i >= j or s[i] == s[j] and f(i + 1, j - 1)\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        a = [-1]\n",
    "        for j, c in enumerate(s):\n",
    "            t = a[-1]\n",
    "            k = j - 1\n",
    "            for i in d[c]:\n",
    "                if a[i] < t and f(i + 1, k):\n",
    "                    t = a[i]\n",
    "            a.append(t + 1)\n",
    "            d[c].append(j)\n",
    "        return a.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        def loop(s):\n",
    "            return s==s[::-1]\n",
    "    \n",
    "        dp = [len(s)-1]*len(s)  #dp[j]代表 s[0:j+1] 这段字符串切割最少需要多少次\n",
    "        loop_dic = {}\n",
    "        dp[0] = 0\n",
    "        for j in range(1,len(s)):\n",
    "            if loop(s[:j+1]):\n",
    "                dp[j] = 0\n",
    "                continue\n",
    "            dp[j] = dp[j-1]+1\n",
    "            for k in range(1,j):\n",
    "                if s[k]!=s[j]:  #剪枝\n",
    "                    continue\n",
    "                if (k,j) not in loop_dic:\n",
    "                    loop_dic[(k,j)] = loop(s[k:j+1])\n",
    "\n",
    "                if loop_dic[(k,j)]:\n",
    "                    dp[j] = min(dp[j],dp[k-1]+1)\n",
    "                if dp[j]==1:\n",
    "                    continue\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # dp[i][j] s[i...j]能否构成回文串\n",
    "        # i:[0,lgh-1] j:[i,lgh-1]\n",
    "        # dp[i][j] = i==j or (j-i+1==2 and s[i]==s[j]) or (j-i+1>2 and s[i]==s[j] and dp[i+1][j-1])\n",
    "        # basecase i==j->True [lgh-1][lgh-1]->True\n",
    "        lgh = len(s)\n",
    "        check = defaultdict(lambda: defaultdict(lambda: False))\n",
    "        for i in range(lgh - 1, -1, -1):\n",
    "            for j in range(i, lgh):\n",
    "                check[i][j] = (i == j) or (j - i + 1 == 2 and s[i] == s[j]) or (j - i + 1 > 2 and s[i] == s[j] and check[i + 1][j - 1])\n",
    "        # dp[i] s[0...i]的最少分割次数\n",
    "        # dp[i] = min(dp[i],dp[j]+1) s[j+1...i]也是回文串\n",
    "        # i:[1,lgh-1] j:[0,i-1]\n",
    "        dp = [float('inf')] * lgh\n",
    "        dp[0] = 0\n",
    "        for i in range(1, lgh):\n",
    "            if check[0][i]:  #本身就是回文则直接0\n",
    "                dp[i] = 0\n",
    "                continue  # 本身不是回文则去前面找 能和i构成回文的 进行状态转移\n",
    "            for j in range(i):\n",
    "                if check[j + 1][i]:\n",
    "                    dp[i] = min(dp[i], dp[j] + 1)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "s.minCut('efe')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        mem = {}\n",
    "\n",
    "        def check(left, right):\n",
    "            if (left, right) not in mem:\n",
    "                if left == right:\n",
    "                    mem[left, right] = True\n",
    "                elif left + 1 == right:\n",
    "                    mem[left, right] = s[left] == s[right]\n",
    "                else:\n",
    "                    mem[left, right] = s[left] == s[right] and check(left + 1, right - 1)\n",
    "            return mem[left, right]\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [[] for _ in range(n)]\n",
    "        dp[0] = [0]\n",
    "        for i in range(1, n):\n",
    "            pres = dp[i - 1]\n",
    "            pre_n = len(pres)\n",
    "            dp[i] = dp[i - 1] + [i]\n",
    "            for j in range(pres[max(0, pre_n - 3)], i):\n",
    "                if check(j, i) and len(lefts := (dp[j - 1] if j > 0 else [])) < len(dp[i]):\n",
    "                    dp[i] = lefts + [j]\n",
    "        return len(dp[-1]) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        itSAPalindromeString = lambda s: s[::-1] == s\n",
    "        dp = [-1, 0]\n",
    "        for i in range(1, len(s)):\n",
    "            dp.append(min([dp[-1]]+[dp[j] for j in range(i) if itSAPalindromeString(s[j: i+1])])+1)\n",
    "        return dp[-1]\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        deq = deque([[s, -1]])\n",
    "        pres = set()\n",
    "        while deq:\n",
    "            cur, h = deq.popleft()\n",
    "            if not cur:\n",
    "                return h\n",
    "            if cur in pres:\n",
    "                continue\n",
    "            pres.add(cur)\n",
    "            for i in range(len(cur), 0, -1):\n",
    "                if cur[:i] == cur[:i][::-1]:\n",
    "                    deq.append([cur[i:], h+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        def valid(i):\n",
    "            return 0 <= i < length\n",
    "        def isPal(i, j, memo = {}):\n",
    "            if i - j in [0, 1]:\n",
    "                return True\n",
    "            if i > j or not valid(i) or not valid(j):\n",
    "                return False\n",
    "            if (i, j) not in memo:\n",
    "                if s[i] == s[j]:\n",
    "                    memo[(i,j)] = isPal(i+1, j-1)\n",
    "                else:\n",
    "                    memo[(i,j)] = False\n",
    "            return memo[(i,j)]\n",
    "\n",
    "        def minCut(j, memo = {0: 0}):\n",
    "            if j not in memo:\n",
    "                if isPal(0, j):\n",
    "                    memo[j] = 0\n",
    "                else:\n",
    "                    memo[j] = min(minCut(i) for i in range(j) if isPal(i+1, j)) + 1\n",
    "            return memo[j]\n",
    "\n",
    "        return minCut(length - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cal(i,j):\n",
    "            if i>j:\n",
    "                return True\n",
    "            return s[i]==s[j] and cal(i+1,j-1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def recur(i):\n",
    "            if i>=len(s):\n",
    "                return 0\n",
    "            return min(recur(j+1)+1 for j in range(i,len(s)) if cal(i,j))\n",
    "\n",
    "        return recur(0)-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = {}\n",
    "        for (k,v) in enumerate(s):\n",
    "            for i in range(k+1):\n",
    "                if k == i:\n",
    "                    dp[(k,i)] = True\n",
    "                else:\n",
    "                    dp[(i,k)] = False\n",
    "                    if v == s[i]:\n",
    "                        if k-1 == i:\n",
    "                            dp[(i, k)] = True\n",
    "                        elif dp[(i+1, k-1)] == True:\n",
    "                            dp[(i,k)] = True\n",
    "        minCnt= math.inf\n",
    "        dp2 = {}\n",
    "        dp2[-1] = 0\n",
    "        for (k,v) in enumerate(s):\n",
    "            pass\n",
    "            val1 = math.inf\n",
    "            if dp[(0,k)]:\n",
    "                dp2[k] = 0\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                if dp[(j+1,k)]:\n",
    "                    val1 = min(val1, dp2[j] + 1 )\n",
    "            dp2[k] = val1\n",
    "        return dp2[len(s)-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "#print(a.minCut('aaba'))\n",
    "print(a.minCut(\"cdd\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        @cache\n",
    "        def check(l, r):\n",
    "            return s[l] == s[r] and (l >= r - 1 or check(l + 1, r - 1))\n",
    "\n",
    "        @cache\n",
    "        def dp(end):\n",
    "            if check(0, end - 1):\n",
    "                return 0\n",
    "            return min(dp(i) for i in range(1, end) if check(i, end - 1)) + 1 \n",
    "        \n",
    "        return dp(len(s))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def is_pal(i, j):\n",
    "            if i > j:\n",
    "                return False\n",
    "            if j - i == 0:\n",
    "                return True\n",
    "            if j - i == 1:\n",
    "                return s[i] == s[j]\n",
    "            return s[i] == s[j] and is_pal(i + 1, j - 1)\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(L):\n",
    "            if is_pal(L, N - 1):\n",
    "                return 0\n",
    "            return min((1 + dp(j + 1) for j in range(L, N - 1) if is_pal(L, j)), default=float('inf'))\n",
    "        N = len(s)\n",
    "        return int(dp(0))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def initPalinDrome(self, s):\n",
    "        dp = {}\n",
    "        n = len(s)\n",
    "        # bound \n",
    "        for i in range(n):\n",
    "            dp[(i, i)] = True\n",
    "        for i in range(n-1):\n",
    "            dp[(i, i+1)] = True if s[i] == s[i+1] else False\n",
    "\n",
    "        # iteration\n",
    "        for d in range(3, n+1):\n",
    "            for left in range(n):\n",
    "                right = left + d -1 \n",
    "                if right >= n: continue \n",
    "                if s[left] == s[right]:\n",
    "                    dp[(left, right)] = dp[(left+1, right-1)]\n",
    "                else:\n",
    "                    dp[(left, right)] = False\n",
    "\n",
    "        return dp\n",
    "        \n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = {}\n",
    "        dp[-1] = -1                                  # NOTE if [0, i] 整个为回文 cut = dp[-1] + 1 \n",
    "        dp[0] = 0\n",
    "\n",
    "        hashmap = self.initPalinDrome(s)\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            dp[i] = i                                     # NOTE 设初值 最多要切割 i 次        \n",
    "            for j in range(i+1):\n",
    "                if hashmap[(j, i)]:          # [j, i]\n",
    "                    dp[i] = min(dp[j-1] + 1, dp[i])\n",
    "        \n",
    "        return dp[n-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
